package 剑指offer;

/**
 * @author: tyy 剑指 Offer
 * 211. 添加与搜索单词 - 数据结构设计
 *请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
    实现词典类 WordDictionary ：
    WordDictionary() 初始化词典对象
    void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
    bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母
    示例：
    输入：
    ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
    [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
    输出：
    [null,null,null,null,false,true,true,true]

 * @create: 2021-10-19 17:40
 * @description:
 **/
public class Solution6 {
    public static int convertBinaryToDecimal(long num)
    {
        int decimalNumber = 0, i = 0;
        long remainder;
        while (num != 0)
        {
            remainder = num % 10; // num最后一位数
            num /= 10;
            decimalNumber += remainder * Math.pow(2, i); // 最后一位是0则是0，是1则是2的i次方
            ++i;
        }
        return decimalNumber;
    }
    public int findComplement(int num) {
        String s = Integer.toBinaryString(num);
        char[] chars = s.toCharArray();
        char[] temps = new char[chars.length];
        for (int i = 0; i < chars.length; i++) {
            temps[i] = chars[i] == '1' ? '0' : '1';
        }
        String s1 = String.valueOf(temps);
        Long value = Long.valueOf(s1);
        int decimal = convertBinaryToDecimal(value);
        System.out.printf("%d 二进制 = %d 十进制", num, decimal);

        return decimal;

    }

    public int findComplement1(int num) {
        long ans=1;
        while(ans<=num){ans*=2;}
        return (int)ans-1-num;

//        int bitCount = 31;
//        while ((num & (1<<bitCount)) == 0) --bitCount; // 统计二进制位数
//        return (~num)&((1<<(bitCount+1))-1);
    }

    public int findComplement2(int num) {
        int t = 1;
        int sum=0;
        while(num>0){
            if((num&1)==0){
                sum+=t;
            }
            t*=2;
            num>>=1;
        }
        return sum;
    }
    public static void main(String[] args) {
        int complement = new Solution6().findComplement(20161211);
        System.out.println("complement = " + complement);
    }
}

